package com.example.demo.arithmetic.datastructure.tree;

import java.util.LinkedList;

// 二叉搜索树的范围和
// 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
//      4
//     / \
//    2   6
//   / \
//  1   3
// low=3
// high=5
public class Leetcode938_3 {
    public int rangeSumBST(TreeNode node, int low, int high) {

        if (node == null) {
            return 0;
        }
        // 剪枝 1 只需要右子树找
        if (node.val < low) {
            return rangeSumBST(node.right, low, high);
        }
        // 剪枝 2 只需要左子树找
        if (node.val > high) {
            return rangeSumBST(node.left, low, high);
        }

        return node.val + rangeSumBST(node.left, low, high) + rangeSumBST(node.right, low, high);

    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(4);
        node.left = new TreeNode(2, new TreeNode(1), new TreeNode(3));
        node.right = new TreeNode(6);
        int rangedSumBST = new Leetcode938_3().rangeSumBST(node, 3, 5);
        System.out.println(rangedSumBST);
    }


}
